package com.hjx.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 *
 */
class LeetCode_51 {

    private List<List<String>> res = new ArrayList<>();


    public List<List<String>> solveNQueens(int n) {
        // bytes 数组表示 n*n棋盘 1表示王后 0表示空 最后将bytes数组转为.Q形式的字符串，每行用逗号分开
        byte[][] bytes = new byte[n][n];
        // 从第一行开始 回溯法暴力求解
        backTrack(bytes, 0);
        return res;
    }

    private void backTrack(byte[][] bytes, int row) {
        // 遍历到棋盘最后一行，每一行都正确放置了皇后
        if (row == bytes.length) {
            res.add(byteToRes(bytes));
            return;
        }

        // 在每行找一个合适的位置放置皇后

        for (int i = 0; i < bytes[row].length; i++) {
            //跳过非法位置
            if (!isValid(bytes, row, i)) {
                continue;
            }
            // 合法位置放置皇后
            bytes[row][i] = 1;
            // 递归进行下一行的处理
            backTrack(bytes, row + 1);
            // 撤销选择
            bytes[row][i] = 0;
        }




    }

    /**
     * 检查3个方向即可 上方 左上 右上， 因为放置皇后是从上往下放  下方 左下 右下 右面 左边 肯定没有
     * @param bytes 棋盘
     * @param row 行
     * @param col 列
     * @return
     */
    private boolean isValid(byte[][] bytes, int row, int col) {
        // 棋盘宽度 遍历最大次数
        int n = bytes.length;
        //检查列是否有皇后存在冲突
        for (int i = 0; i < n; i++) {
            if (bytes[i][col] == 1 ) {
                return false;
            }
        }
        //右上方
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (bytes[i][j] == 1 ) {
                return false;
            }
        }
        //左上方
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (bytes[i][j] == 1 ) {
                return false;
            }
        }


        return true;
    }

    /**
     * bytes数组转换为一种棋盘的放置方法
     * @param bytes
     * @return
     */
    private List<String> byteToRes(byte[][] bytes) {
        List<String> strings = new ArrayList<>();
        for (int i = 0; i < bytes.length; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < bytes[i].length; j++) {
                if (bytes[i][j]==1) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            strings.add(sb.toString());
        }
        return strings;
    }
}
